#-*-coding:utf-8-*-
#author:fanerlei
# https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/
# 拷贝复杂链表

# Definition for a Node.
class Node:
    def __init__(self, x, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random
# 为什么Node可以作为Dict的key

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        tmpDict = {}
        curNode = head
        if not head:
            return None
        while(curNode):
            tmpDict[curNode] = Node(curNode.val)
            curNode = curNode.next
        curNode = head
        while(curNode):
            tmpDict[curNode].next = tmpDict.get(curNode.next)
            tmpDict[curNode].random = tmpDict.get(curNode.random)
            curNode = curNode.next

        return tmpDict.get(head)